{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "e2650339",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# O(1)\n",
    "\n",
    "def constant_time(arr):\n",
    "   return arr[0] if arr else None\n",
    "\n",
    "constant_time([1,3,5])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "4d910396",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# O(log(n))\n",
    "\n",
    "def binbary_search(arr, target):\n",
    "   left, right = 0, len(arr) - 1\n",
    "   while left <= right:\n",
    "       mid = (left + right) // 2\n",
    "       if arr[mid] == target:\n",
    "           return mid\n",
    "       elif arr[mid] < target:\n",
    "           left = mid + 1\n",
    "       else:\n",
    "           right = mid - 1\n",
    "   return -1\n",
    "\n",
    "binbary_search([1,3,5],5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "350cfdf3",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# O(n)\n",
    "def linear_search(arr, target):\n",
    "   for i, value in enumerate(arr):\n",
    "       if value == target:\n",
    "           return i\n",
    "   return -1\n",
    "\n",
    "linear_search([1,3,5],5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "170968e3",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 3, 5]"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# O(n log n)\n",
    "\n",
    "def merge_sort(arr):\n",
    "   if len(arr) <= 1:\n",
    "       return arr\n",
    "   mid = len(arr) // 2\n",
    "   left = merge_sort(arr[:mid])\n",
    "   right = merge_sort(arr[mid:])\n",
    "   return merge(left, right)\n",
    "\n",
    "def merge(left, right):\n",
    "   result = []\n",
    "   i, j = 0, 0\n",
    "   while i < len(left) and j < len(right):\n",
    "       if left[i] <= right[j]:\n",
    "           result.append(left[i])\n",
    "           i += 1\n",
    "       else:\n",
    "           result.append(right[j])\n",
    "           j += 1\n",
    "   result.extend(left[i:])\n",
    "   result.extend(right[j:])\n",
    "   return result\n",
    "\n",
    "merge_sort([3,5,1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "e17fe16b",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 3, 5]"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# O(n^2)\n",
    "def bubble_sort(arr):\n",
    "   n = len(arr)\n",
    "   for i in range(n):\n",
    "       for j in range(0, n - i - 1):\n",
    "           if arr[j] > arr[j + 1]:\n",
    "               arr[j], arr[j + 1] = arr[j + 1], arr[j]\n",
    "   return arr\n",
    "\n",
    "bubble_sort([3,5,1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "476e56d9",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "55"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# O(2^n)\n",
    "\n",
    "def fibonacci(n):\n",
    "   if n <= 1:\n",
    "       return n\n",
    "   return fibonacci(n-1) + fibonacci(n-2)\n",
    "\n",
    "fibonacci(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "56a80eda",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
